class Solution {
public:
    void dfs(vector<int>& nums, int index)
    {
        if (index == nums.size())
        {
            if (sum == _target)
                ret++;
            return;
        }
        
        int tmp = nums[index];

        sum += tmp;
        dfs(nums, index + 1);
        sum -= tmp;

        sum += -1 * tmp;
        dfs(nums, index + 1);
        sum -= -1 * tmp;
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        _target = target;
        dfs(nums, 0);

        return ret;
    }
private:
    int ret = 0;
    int _target;
    int sum = 0;
};
